The multistage interconnection network (MIN) is a popular topology for communication and computer networks. The most basic MIN is the three-stage Clos network which is often used as a component for larger networks. One important performance criterion for an interconnection network is its blocking probability. In particular, a zero blocking probability, or non-blockness, is a highly desirable property.
There are generally three types of non-blocking circuits: strictly non-blocking; wide sense non-blocking; and rearrangeable non-blocking. In a rearrangeable non-blocking network, connectivity is guaranteed as a result of the network's ability to rearrange prior connections as new incoming calls are received. A critical issue in designing a rearrangeable non-blocking network is to reduce the number of center stage interconnection units necessary to provide the rearrangeability function and thereby guarantee connectivity for each received request. The prior art has recognized that a rearrangeable non-blocking network can have as little as 3N center stage interconnection units, where N is the greater of the number of inlets per input switch or outlets per outlet switch, as described below.
Each request, which includes all types of communications such as a telephone call and a data communication, is associated with a weight or load which can be thought of as the bandwidth requirement of that request. In a multi-rate environment these loads differ for different requests. A link, whether inlet, outlet or internal, can carry any number of requests as long as the combined load of these requests does not exceed the load capacity of the link.
Each request can be represented mathematically with the three variables x, y, and w, where x is an inlet link, y an outlet link and w is its load. A request frame is a collection of requests such that the total load of all requests in the frame involving a fixed inlet or outlet does not exceed unity.
To discuss routing it is convenient to assume that all links are directed from left to right. Thus a path from an inlet to any outlet always consists of the sequence: an inlet link.fwdarw.an input switch.fwdarw.a first internal link.fwdarw.a center interconnection unit.fwdarw.a second internal link.fwdarw.an output switch.fwdarw.an outlet link. Since the switch is assumed to be nonblocking with fan-out properties i.e., one inlet can be simultaneously connected to any set of outlets, a request (x, y, w) is routable only if there exists at least one path of links from x to y, where every link on the path can carry the load of the request without exceeding its load capacity. In other words, every link on the path must have unused capacity of at least 1-w before carrying the request. A request frame is routable if there exists a set of paths, one for each request, such that for every link the sum of the loads of all requests being carried on that which does not exceed unity. A network is rearrangeable non-blocking if every request frame is routable.
A critical implementation issue in rearrangeable nonblocking networks is the number of center stage interconnection units necessary to provide the rearrangeable nonblocking function. It is desired to identify and thus construct a switching network having a reduced number of center stage interconnection units while achieving the property of being rearrangeable nonblocking.